1. Field of the Invention
The present invention relates to a decoder for performing iterative decoding of binary cyclic codes.
2. Description of the Related Art
Cyclic codes are attractive because encoding can be performed systematically and can also be easily implemented using shift-registers with feedback connections.
Iterative soft-decision decoders use the values of the matched filter outputs in a digital receiver. This contrasts with hard-decision decoders, which use bits based on the sign of the matched filter outputs. Soft decision decoders have better performance than hard-decision decoders, of about 2 dB improvement in bit signal-to-noise ratio. A soft-decision decoder for a binary cyclic code uses the Viterbi algorithm applied to a trellis.
It is conceivable to make a soft-decision decoder for decoding many different binary cyclic codes. However, such a conceivable decoder would require a different trellis structure for each cyclic code. This would require a great deal of memory and hardware, because different trellises have different sizes, that is, the number of states and number of branches, and also different structures.
It is desirable if a single decoder configuration could be used for decoding more than a specific family of binary cyclic codes.
The present inventor has discovered that iterative decoding of (n,k) binary cyclic codes based on belief propagation produces only poor results. These poor results are thought to be because an (n-k)-by-n parity-check matrix of an (n,k) binary cyclic code has columns with very low Hamming weights, that is, with only one nonzero element.
It is also desirable to produce a decoder that can decode binary cyclic codes using iterative decoding based on belief propagation with good results and using a simple configuration.
It is an objective of the present invention to provide a decoder capable of decoding many different families of cyclic codes.
It is another objective of the present invention to produce a decoder that can decode binary cyclic codes using iterative decoding based on belief propagation with good results.
A decoder according to the present invention is for decoding a data stream from a noisy channel into estimated bits. Before the data stream was transmitted across the noisy channel, it was encoded by an encoder according to a cyclic code into a plurality of code words in sequence.
In order to achieve the above-described objectives, the decoder according to the present invention includes an input means, a scaler, a Z processor, an X processor, and an information exchange control unit.
The input means receives input of a vector of noisy received values r(i) (where 0xe2x89xa6ixe2x89xa6nxe2x88x921) of the data stream, a code length n of the code words, and a parity-check polynomial h(x) corresponding to the cyclic code. The parity-check polynomial h(x) has J-number of nonzero coefficients.
The scaler multiplies each noisy received value r(i) by a constant, and outputs each product as a log-likelihood ratio LLR(i).
The Z processor receives n-sets of xcfx80z(i,j) metrics (where 0xe2x89xa6jxe2x89xa6Jxe2x88x921), each set including J-number of xcfx80z(i,j) metrics. The Z processor calculates n-sets of xcexz(i,j) metrics based on the xcfx80z(i,j) metrics, each set including J-number of xcexz(i,j) metrics.
The X processor receives n-sets of xcexx(i,j) metrics, each set including J-number of xcexx(i,j) metrics. The X processor calculates n-number of a-posteriori values q(i) based on the xcexx(i,j) metrics and the log-likelihood ratios LLR(i). The X processor calculates n-sets of xcfx80x(i,j) metrics based on the xcexx(i,j) metrics and the a-posteriori values q(i), each set including J-number of xcfx80x(i,j) metrics. The X processor determines n-number of estimated code bits i based on the a-posteriori values q(i).
The information exchange control unit distributes the xcfx80x(i,j) metrics based on a cyclic shift of the parity-check polynomial h(x) to produce the xcfx80z(i,j) metrics. The information exchange control unit distributes the xcexz(i,j) metrics based on a reverse order of the cyclic shift of the parity-check polynomial h(x) to produce the xcexx(i,j) metrics.
With this configuration, iterative soft decision decoding can be performed using the same simple configuration to decode cyclic codes from many different families of cyclic codes. Binary cyclic codes can be iteratively decoded based on belief propagation with good results.
It is desirable that the decoder further include a xcfx80 RAM and a xcexRAM. The xcfx80 RAM is connected to an output of the X processor and an input of the Z processor. The xcexRAM is connected to an output of the Z processor and an input of the X processor.
The information exchange control unit organizes the xcfx80 RAM into a J-by-n array with J columns and n rows based on the inputted code length n and the inputted parity-check polynomial h(x). The information exchange control unit distributes the xcfx80x(i,j) metrics from the X processor into the xcfx80 RAM based on the cyclic shift of the parity-check polynomial h(x), and transfers to the Z processor the J-number of xcfx80x(i,j) metrics in each column of the xcfx80 RAM as one of the n-sets of xcfx80z(i,j) metrics.
The information exchange control unit organizes the xcexRAM into a J-by-n array with J columns and n rows based on the inputted code length n and the inputted parity-check polynomial h(x). The information exchange control unit distributes the xcexz(i,j) metrics from the Z processor into the xcexRAM based on the reverse order of the cyclic shift of the parity-check polynomial h(x), and transfers to the X processor the J-number of xcexz(i,j) metrics in each column of the xcexRAM as one of the n-sets of xcexx(i,j) metrics.
With this configuration, the decoder according to the present invention can be realized in a serial configuration, using a minimal of hardware.
Alternatively, it is desirable that the decoder further includes a bus connecting the Z processor, the X processor, and the information exchange control unit to each other. In this case, the Z processor includes n-number of Zi processors each connected to the bus with an individual address, and the X processor includes n-number of Xi processors each connected to the bus with an individual address. The information exchange control unit includes an address computation unit for transferring, across the bus, the xcfx80x(i,j) metrics from the Xi processors as xcfx80z(i,j) metrics to Zi processors determined based on the cyclic shift of the parity-check polynomial h(x) and the xcexz(i,j) metrics from the Zi processors as xcexx(i,j) metrics to Xi processors determined based on the reverse order of the cyclic shift of the parity-check polynomial h(x).
With this configuration, the decoder according to the present invention can be realized in a fast parallel configuration.
It is desirable that the Z processor compute the xcexz(i,j) metrics based on:
xcexz(i,j)=(xe2x88x921)xcex4⊕sgn (xcfx80z(i, j))(Sxe2x88x92FQ(|xcfx80z(i,j)|)) 
wherein:       S    =                            (                      -            1                    )                δ            ⁢                        ∑                      j            =            0                                J            -            1                          ⁢                              F            Q                    ⁡                      (                          |                                                π                  z                                ⁡                                  (                                      i                    ,                    j                                    )                                            |                        )                                ,
xcex4=(xe2x88x921)⊕j=0jxe2x88x921sgn (xcfx80z(i,j)), and p1 FQ (x) denotes a quantized version of the function F(x)=log[(ex+1)/(exxe2x88x921)].
With this configuration, the xcexz(i,j) metrics can be reliably computed. In this case, it is desirable that the Z processor computes the xcexz(i,j) metrics using the following quantized version FQ (x) of the function F(X)=log[(ex+1)/(exxe2x88x921)], because almost the same results can be obtained as with no quantization, but with much simpler computations:             F      Q        ⁡          (      x      )        =      {                                        5.00            ,                                                              xe2x80x83                        ⁢                                          0                ≤                x                ≤                0.10                            ;                                                                        2.25            ,                                                              xe2x80x83                        ⁢                                          0.10                ≤                x                ≤                0.35                            ;                                                                        1.50            ,                                                              xe2x80x83                        ⁢                                          0.35                ≤                x                ≤                0.60                            ;                                                                        1.00            ,                                                              xe2x80x83                        ⁢                                          0.60                ≤                x                ≤                0.90                            ;                                                                        0.75            ,                                                              xe2x80x83                        ⁢                                          0.90                ≤                x                ≤                1.20                            ;                                                                        0.50            ,                                                              xe2x80x83                        ⁢                                          1.20                ≤                x                ≤                1.60                            ;                                                                        0.30            ,                                                              xe2x80x83                        ⁢                          1.60              ≤              x              ≤              2.30                                                                        0.10            ,                                                              xe2x80x83                        ⁢                          2.30              ≤                              x                .                                                        
It is desirable that the X processor calculate the a-posteriori values q(i) based on             q      ⁡              (        i        )              =                            ∑                      j            =            0                                J            -            1                          ⁢                              λ            x                    ⁡                      (                          i              ,              j                        )                              +              L        ⁢                  xe2x80x83                ⁢        L        ⁢                  xe2x80x83                ⁢                  R          ⁡                      (            i            )                                ,
calculate the xcfx80x(i,j) metrics based on xcfx80x(i,j)=q(i)xe2x88x92xcexx(i, j), and determine the n-number of estimated code bits based on i=sgn (q(i)). With this configuration, the a-posteriori values q(i) can be reliably calculated.
It is desirable that the constant used by the scaler equals 4/spectral density No of the noisy channel. With this configuration, overflow, which occurs when probabilities of a xe2x80x9c0xe2x80x9d or a xe2x80x9c1xe2x80x9d are too close to 1 or 0, can be reliably prevented from occurring.
It is desirable that the input means further receives input of a fixed number of iterations. In this case, the X processor determines the n-number of estimated code bits i after the fixed number of iterations. With this configuration, decoding delay is fixed. As a result, no buffers are required when data is delivered to its destination, so that hardware configuration is simpler.
It is desirable that the information exchange control unit perform the cyclic shifts of the parity-check polynomial h(x) by multiplying successive ones of x0 to xnxe2x88x921 times the parity-check polynomial h(x) and performs the reverse order of the cyclic shifts of the parity-check polynomial h(x) by multiplying successive ones of x0 to xnxe2x88x921 times the reciprocal hxe2x88x921(x) (xn h(xxe2x88x921)) of the parity-check polynomial h(x). With this configuration, there is no need to store the entire parity-check matrix; the parity-check polynomial and the code length are all that need to be inputted.
It is desirable that, in a first iteration, the X processor makes preliminary hard decisions on the a-posteriori values q(i) to produce hard decision values for highly reliable positions. In this case, the information exchange control unit uses the hard decisions when distributing the xcfx80x(i,j) metrics and the xcexz(i,j) metrics. With this configuration, decoding can be performed much more easily without any significant increase in decoding errors. In this case, it is desirable that the Z processor makes the preliminary hard decisions based on whether a a-posteriori value q(i) exceeds a threshold T, because this enables designating highly reliable positions with a simple configuration.